package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SearchForARange {

	public static void main(String[] args) {

		int nums[]={5, 7, 7, 8,8, 8, 10};
		int target=9;
		int [] res=searchRange(nums, target);
		for(int i=0;i<res.length;i++){
			System.out.println(res[i]);
		}
	}

	public static int[] searchRange(int[] nums, int target) {

		List<Integer> result=new ArrayList<Integer>();
		int left=0,right=nums.length-1,mid;
		int targetIndex=0;
		while(left<=right){
			mid=(left+right)/2;
			if(nums[mid]==target){
				targetIndex=mid;
				//result.add(targetIndex);
				break;
				
			}else if(nums[mid]>=target){
				right=mid-1;
			}else{
				left=mid+1;
			}
		}
		if(left>right){ result.add(-1);result.add(-1);}
		else{
		int flag=targetIndex,tip=targetIndex+1;
		while(flag>=left&&flag<=targetIndex){
			if(nums[flag]==target)
				flag--;
			else break;
		}
		result.add(++flag);
		
		while(tip<=right&&tip>=targetIndex){
			if(nums[tip]==target)
				tip++;
			else break;
		}
		result.add(--tip);
		}
		int[] res=new int[result.size()];
		for(int i=0;i<result.size();i++){
			res[i]=result.get(i);
		}
		return res;
		
	}
}
